The present invention relates generally to content addressable memories (CAMs) and more particularly to a novel CAM architecture that allows for a longest prefix matching function.
Information network systems continue to proliferate. Typically network data is transferred in data structures referred to as xe2x80x9cpackets.xe2x80x9d A packet can travel through network according to information included in a portion of the packet referred to as a xe2x80x9cheader.xe2x80x9d Network switches and/or routers can receive packets, extract information from the packet header, and process the packet according to the extracted information. Network header information can establish, to name just a few possible examples, the destination of a packet and/or the manner in which a packet should be transmitted.
Packet routing and/or switching typically utilizes a matching function. In a matching function, a header field will be compared to a number of entries. In the event the field (or a portion of the field) matches an entry, a match indication will be generated. The match indication can be used to generate particular processing information for the packet.
Routing and switching functions can be performed by general-purpose processors that run a routing algorithm. Such an approach can result in limited throughput of data packets, be expensive in terms of component cost, and require considerable area to implement when implemented as one or more integrated circuits.
One way to address the need for faster routers is to fabricate an integrated circuit that is specialized to perform routing/switching tasks. Such application specific integrated circuits (ASICs) are designed to perform particular routing functions such as a matching function in conjunction with a random access memory (RAM). Unfortunately, because ASICs are custom manufactured products, they can also be expensive to manufacture.
One type of device that is particularly suitable for matching functions is a content addressable memory (CAM) (also referred to as an xe2x80x9cassociative memoryxe2x80x9d). A CAM can include a number of data storage locations, each of which can be accessed by a corresponding address. The order in which the data values are stored varies according to the type of CAM. As just one example, in a typical xe2x80x9cbinaryxe2x80x9d CAM, data can be stored in the first available xe2x80x9cemptyxe2x80x9d location. Empty locations can be distinguished from xe2x80x9cfullxe2x80x9d (or valid) locations by a status bit associated with each storage location.
Valid locations in a binary CAM can be addressed according to the contents (data values) that they store. In a typical binary CAM matching function, a comparand value (which can be a header field or a portion thereof) can be loaded into a comparand register. The comparand value can then be compared to the data values within each valid location of the conventional binary CAM. In the event the value within the comparand register matches a value of a storage location, a match signal for the matching storage location will be generated. In the event there is more than one match, one match from the multiple matches may be selected according to predetermined priority criteria. The match indication can then be used to access other information (such as routing or packet processing information, as just two examples).
By providing for the simultaneous comparison of a comparand word value (a row of comparand bit values) with a number of data words, a rapid match function can be accomplished with a binary CAM. One drawback to conventional binary CAMs is that matching functions are typically performed on data values having a fixed number of bits. Unfortunately, many routing and switching functions can require matching a comparand value to data values having variable bit lengths.
An example of longest prefix matching operation will be described below. Two data values (data0 and data1) are set forth. The data values (data0 and data1) are binary values having portions that can be compared to a comparand value (shown as either a 0 or 1). In addition, the data values (data0 and data1) have portions that do not have to be matched. These xe2x80x9cnon-matchxe2x80x9d portions are represented by a series of Xs. It is understood that each X could be a 0 or 1, but is represented by an X because the digit should not be compared with a comparand value.
For the example of the data values set forth above, if the following comparand value is applied:
Both data values can result in a match indication. It is preferred that the data 1 value match indication have priority as it provides the longest prefix match.
One type of device that can be particularly suitable for longest prefix matching is a xe2x80x9cternaryxe2x80x9d or xe2x80x9ctertiaryxe2x80x9d CAM. In a conventional ternary CAM, a mask bit is provided for each data bit. When the mask bit has a first predetermined value (a logic low, for example) its corresponding data bit will be masked from a compare operation. When a data bit is masked, it will not be compared with an applied comparand value. Ternary CAM entry values are set forth below for the two examples previously described.
To better understand the present invention, and to more clearly distinguish the described embodiments from conventional CAM approaches, a conventional ternary CAM is cell is set forth in FIG. 16. The conventional ternary CAM cell is designated by the general reference character 1600, and is shown to include data register 1602, a compare circuit 1604, a mask register 1606, and a mask circuit 1608. Data values can be entered into the data register 1602 by placing data values on a bit line pair (B and /B) and activating a data word line DWL. Similarly, mask values can be entered into the mask register 1606 by placing data values on a bit line pair (B and /B) and activating a mask word line MWL. It is understood that the word lines (DWL and MWL) can be commonly coupled to a row of CAM cells and the bit line pair (B and/B) can be commonly coupled to a column of CAM cells.
The compare circuit 1604 can receive the data value stored within the data register 1602 by way of complementary data lines D and /D and a complementary comparand values by way of compare lines C and /C. The compare circuit 1604 compares the data value and comparand value, and in the event the values are different, activates a match indication on match line M. In the particular conventional example of FIG. 16, the compare circuit 1604 is an exclusive OR (XOR) or exclusive NOR (XNOR) circuit.
Unlike a conventional binary CAM cell, which would couple comparison results of a compare circuit directly to a match line, in the conventional ternary CAM cell 1600, comparison results can be masked by the mask circuit 1608. In the event the mask register 1606 includes an active mask data bit (M), the mask circuit 1608 can prevent a comparison result from affecting the match line xe2x80x9cMATCH.xe2x80x9d
FIG. 17 illustrates an example of a conventional register that may be used in a CAM (as item 1602 or 1606 in FIG. 16, as just one example). The register is designated by the general reference character 1700. Complementary stored data values stored within register 1700 are provided at data nodes 1702-0 and 1702-1. Data values can be set within the register 1700 by driving a bit line pair (B and /B) to complementary data values and activating a corresponding word line WL.
FIG. 18 sets forth a conventional compare circuit 1800 that may be used in a CAM (as item 1604 in FIG. 16, as just one example). The compare circuit 1800 can receive complementary data values (D and /D) and complementary comparand values (C and /C). An indication node 1802 can be precharged to a high logic level at the beginning of a compare operation. A data value (D and /D) and comparand value (C and /C) can then be applied to the compare circuit 1800. In the event the data value (D and /D) is different form the comparand value (C and /C), the indication node 1802 will be discharged to a low logic level (VSS). In the event the data value (D and /D) matches the comparand value (C and /C), the indication node 1802 can remain charged, indicating a match condition. The indication node 1802 can be common to a number of CAM cells of the same row. Thus, an indication node 1802 that remains precharged after a match operation can indicate a match between a row of comparand values and a row of data values (i.e., function as a match line).
A conventional mask circuit (such as item 1608 of FIG. 16) can be formed with an insulated gate field effect transistor (IGFET) having a gate connected to mask value M (or inverse mask value /M).
In the operation of a conventional ternary CAM, a comparand word value can be applied to multiple data word values, each of which can be masked at the bit level. In the event multiple matches exist, the match having the longest prefix can be given priority. Conventionally, priority can be established by placing the data values within the ternary CAM in a predetermined order. As just one example, in a ternary CAM having data locations that start with 0 and end with xe2x80x9cnxe2x80x9d, data values can be stored in order of prefix length. Thus, a match corresponding to the lowest data location will represent the longest prefix match. Alternatively, a processor system, or the like, can maintain a record of the prefix lengths for each entry, and determine priority accordingly. In any event, for longest prefix matching operations, ternary CAM entries must be maintained in a predetermined order and/or a record can be maintained of prefix lengths according to location. This can result in complex data value management systems that can be expensive and/or time consuming to implement.
The need to maintain a particular order to ternary CAM entries can have a considerable impact on network and switch operations. Every time a new entry is entered into a conventional ternary CAM (a route table is xe2x80x9cupdatedxe2x80x9d), the order of data values may have to be rearranged. For example, for a conventional ternary CAM where data values are ordered according to prefix length, when a new data value is entered, those data values having smaller prefixes will have to be shifted down. Further, many routers and/or network switches can include a memory that mirrors the ternary CAM value entries. Such a mirroring memory will also have to be updated. Thus, the updating of routing tables can consume valuable time due to the large number of data values that have to be moved. In some high-throughput router/switches, hundreds of such updates can occur per second.
It would be desirable to arrive at some sort of approach that could not only provide a longest prefix matching function, but could also be capable of reducing the time required to update data values (such as a routing table) in a longest prefix match system.
According to one embodiment of the present invention, a novel content addressable memory (CAM) can provide a longest prefix matching operation that does not necessarily require the data values to be stored in a particular order. A longest prefix matching operation can include a ternary match operation in which a comparand value is applied to data values having corresponding mask values. The ternary match operation may result in multiple match results of various prefix lengths. The mask data from the match results can be used to indicate a longest prefix value. The longest prefix value can be compared to the mask data of the multiple match results to indicate a longest prefix match.
According to one aspect of an embodiment, the novel CAM can include CAM cells arranged in an array having rows and columns. Each CAM cell can store a mask bit. A longest prefix bit value can be compared to the mask bit values of the same column.
According to another aspect of an embodiment, the CAM cells can include a data compare circuit that can compare a comparand value to a stored data bit value, and a mask compare circuit that can compare a stored mask data bit value to a longest prefix bit value.
According to another aspect of an embodiment, each row of CAM cells can further include data CAM cells and encoded prefix/mask data CAM cells. Data CAM cells can compare a stored data bit value to a comparand bit value according to a stored mask bit value. Encoded prefix/mask data CAM cells can store encoded data that represents the mask bit values of the data CAM cells within its row. Prefix/mask data from ternary match results can be used to generate an encoded longest prefix value. The encoded longest prefix value can be compared to the prefix/mask data CAM cells of the multiple match results to indicate a longest prefix match.
According to another aspect of an embodiment, in a ternary mode of operation, the mask data of match results can be detected by xe2x80x9cprefixxe2x80x9d bit lines disposed in the column direction.
According to another aspect of an embodiment, prefix bit lines can also function as data bit lines. Data bit lines can be used to read (or write) a data bit and/or a mask value bit from (or into) a CAM cell.
According to another aspect of the above embodiment, a novel CAM cell can be coupled to a match line common to a row of CAM cells and a prefix bit line common to a column of CAM cells. A CAM cell can provide mask data by driving its prefix bit line toward a predetermined logic value when its mask bit is inactive and its match line is active.
According to another aspect of the above embodiment, prefix bit lines can be arranged as xe2x80x9cwire-ORxe2x80x9d (or xe2x80x9cwire-NORxe2x80x9d) circuits. A prefix bit line can be precharged to one logic level. Each CAM cell can include a prefix bit detect circuit. Each prefix bit detect circuit can connect its prefix bit line to a second logic level by a first controllable impedance path and a second controllable impedance path arranged in series with one another. The first controllable impedance path can be controlled by a xe2x80x9chitxe2x80x9d line common to a row of CAM cells that is activated by a match indication for the row of CAM cells. The second controllable impedance path can be controlled by the mask bit of the CAM cell.
According to another aspect of an embodiment, each novel CAM cell can be coupled to a match line. The novel CAM cells can include a mask data compare circuit having a discharge (or charge) path that is controlled by a comparison result between a data bit and a longest prefix value bit. The longest prefix value bit can be common to at least a column of CAM cells.
According to another aspect of an embodiment, the CAM includes CAM cells arranged into a number of columns. The CAM cells of the same column can receive complementary longest prefix bit values. Global masks can be applied to the CAM cells on a column-wise basis by driving the complementary longest prefix bit values of the column to the same logic level.
According to another aspect of an embodiment, the CAM can include multiple arrays of CAM cells. The mask data of the match results from multiple arrays can be combined to indicate the length of the longest prefix value for all arrays.